The present invention relates to cross correlators, and in particular, to cross correlator techniques for use in communication systems.
In communication systems, incoming signals are sometimes cross correlated with reference patterns to extract meaningful information about the incoming signals. This process may be implemented with the use of cross correlators. Cross correlators are electronic circuits wherein data may be compared and a correlation between two data elements obtained. Cross correlators are used in a variety of applications. In a digital application, a sequence of data values, each represented as a plurality of digital bits may be cross correlated with another sequence of data values to determine the correlation between the values (e.g., are the sequences the same or different, and by how much). In wireless communication applications, one sequence of data values may be stored on a system receiving data over a wireless channel. The sequence of data values stored on the receiving system is sometimes referred to as a reference pattern. Data values received over a wireless channel may be cross-correlated with the reference pattern, and the cross-correlation result used for a variety of processing functions.
FIG. 1 illustrates an example of a reference pattern. Reference patterns are comprised of an array of reference values. Generally, these reference values are floating point numbers (e.g., decimals), and each may be represented as digital data values. As an incoming signal is received by a cross correlator, these reference values may be cross correlated with the incoming samples, which may also be represented as digital data values. As data values are received, the sequence of received data may be cross-correlated with the reference pattern. If a peak is generated at the output of the cross correlator, then the sequence of received data being correlated is well correlated with the reference pattern. This is sometimes called a correlation peak.
FIG. 2 illustrates an example of a typical cross correlator circuit. Circuit 200 comprises multipliers 201 through 205, delays 211 through 214, and adders 221 through 224. This example illustrates cross correlation of 128 received data values with a 128 value reference pattern using 128 multipliers, and corresponding delays and adders. The input signal is coupled to a first input of multipliers 201 through 205. The input of multiplier 201 is further coupled to reference value P0 while the output is coupled to the input of delay 211. The input of multiplier 202 is further coupled to reference value P1, while the output is coupled to the input of adder 221. The other input of adder 221 is coupled to the output of delay 211, and the output of adder 221 is coupled to the input of delay 212. The input of multiplier 203 is further coupled to reference value P2, and the output is coupled to the input of adder 222. The input of adder 222 is further coupled to the output of delay 212, and the output is coupled to the input of delay 213. The input of multiplier 204 is coupled to reference value P126, and the output is coupled to the input of adder 223. The other input of adder 223 is coupled to the output of the previous delay in the circuit. The input of multiplier 205 is coupled to reference value P127, and the output is coupled input of adder 224. The other input of adder 224 is further coupled to the output of delay 214, and the output of adder 224 is the output of circuit 200.
Circuit 200 may calculate the correlation between an incoming signal and the reference pattern comprised of reference values P0 through P127. During the first clock cycle, the first data value of the incoming signal (“i0”) is received by the plurality of multipliers 201 through 205 and multiplied by the reference values. For instance, multiplier 201 receives the first input sample and reference value P0, multiplier 202 receives the first input sample and reference value P1, and so on up to multiplier 205, which receives the first input sample and reference value P127. The outputs from multipliers 201 through 204 are coupled to delays 211 through 214. These delays are used to delay a received input for one clock cycle. Therefore, the results from multipliers 201 through 204 are not used in the calculation for the output of circuit 200 during the first clock cycle. However, the value stored in delay 214 may be used in calculating the output in the second clock cycle. The result transmitted from the output of circuit 200 for the first input clock cycle is the result of multiplier 205. In the next cycle, the second sample of the incoming signal is received by multipliers 201 through 205. The multiplication results from the first sample stored in delays 211 through 214 may be added to the multiplication results from the second sample during the second clock cycle. For example, adder 224 may add the second sample result generated from multiplier 205 with the first sample result generated from multiplier 204. This result may be transmitted from the output of circuit 200 for the second cycle while the results from the other multipliers may have their results stored in delays 211 through 214. This process may continue until all the samples of the input signal have been processed by cross correlator circuit 200. If 128 received data values (i0 . . . i127) match the 128 reference pattern values (P0 . . . P127), then the output of cross correlator 200 will peak when the last received data value, P127 is received and processed by multiplier 127 and adder 124. If the output signal of circuit 200 contains a correlation peak, then the input signal and the reference pattern are said to be correlated. This may occur if the values match exactly, but cross correlation may also be used as a measure of similarity between the two sequences, and this may be represented by the magnitude of the correlation peak.
However, one problem with the reference pattern shown in FIG. 1 is that when an incoming signal is cross correlated with a floating point number, the cross correlator becomes extraordinarily complex. Floating point numbers require complicated multipliers, which require a high degree of complexity to implement, and are also expensive and bulky. This may increase the size of the cross correlator, and thereby increase the cost. Given the size and complexity of cross correlator circuits, it is desirable to simplify the cross correlator, resulting in savings in size, complexity, and cost. As illustrated below, reducing the complexity of cross correlation circuits is particularly important in complex communication systems such as wireless communication systems.
Thus, there is a need for improved circuits and methods of simplifying cross correlators. The present invention solves these and other problems by providing improved cross correlation circuits and methods.